Recursion means solving by self reference. Lets take an example. Find the sum of first n natural numbers.
The Gossip Problem - Everyone knows something that nobody else knows. But everybody else wants to know! That's why we need gossip. To make that a bit more mathematical: person #1, 2, 3, ..., n each know a unique piece of information. When two people talk, they “gossip”, exchanging all the pieces of information they have acquired. How many conversations (with two people at a time) are necessary in order that everyone will know all the information?
With 1 person it's too easy: no talking is necessary, the 1 person already knows everything. With 2 people it's still pretty easy: one conversation and they exchange their information. How about with 3 people? One conversation clearly isn't enough. Can they do it with 2, or do they need all three?
With four people things start to get interesting. There are 6 possible conversations: are they all necessary? What strategies can you use to avoid unnecessary conversations?
What happens with five people?
Can you find a strategy with n people that, instead of the (n2 – n)/2 possible conversations, takes a lot less - like only 2n?
Can you, at least for large n, do it with 2n – 1? How about 2n – 3? Can you do 2n – 4?
Can you beat 2n – 4?
Can you write a recursive program for solving this?
What if everyone has a cell phone and can talk to one other person at a time? How do you minimize the total amount of time it takes to finish? (You don't want people waiting around for other people to make a bunch of calls.)
Instructor Notes: Discuss the normal solution (cyclical) and then recursive f(n+1)=f(n)+2
Breaking a Dollar
Our first problem is to figure out how many ways there are to make change for a dollar.
How many ways are there to make change for a dollar? No, really, think about it before moving on to the next problem. Even if you don't have a method, at least list a few ways, make a reasonable estimate with a reason for your estimate, and so on.
OK, let's simplify the problem. How many ways are there to make change for a dollar if the only coins in the world are pennies?
Now what if there are nickels and pennies?
Can you generalize: how many ways are there to make n cents using only nickels and pennies?
Now what if there are dimes, nickels, and pennies? It might help to make an organized table, of the ways of making each amount up to a dollar (maybe in multiples of 5 cents) using dimes, nickels and pennies.
Instructor Notes: Introduce the notion of recursion, and walk students through how to think about it. Help them arrive at P(n)=1; N(n)=P(n)+N(n-5); D(n)=N(n)+D(n-10) with all values being 1 for n=0 and 0 for n<0
Help organize a table to illustrate how this works on a board
Now add in quarters. Do you want to allow half dollars? Dollar coins?
See if students can get to Q(n)=D(n)+Q(n-25) by themselves
Help organize a table to illustrate how this works on a board
Instructor Notes: Help organize the same thing on an Excel spreadsheet. Make sure kids understand the formulae, and explain some cells in terms of which cells they are referencing
Answer with up to quarters is 242
Ask kids what they would do with half dollars and dollars
Homework:
Gossip Problem: What if your goal, rather than minimizing the total number of conversations, is to minimize the maximum number of conversations that any one person has to participate in? Then how do you do it, how many total conversations does it take, and what is the maximum for one person?
Breaking a Dollar:
What if each arrangement (permutation) of the coins was counted differently? What would you have to change to produce the other answer
Let students think about how to account for all permutations
If they are unable to think through, help them get to a conclusion that we can "reduce" the problem just by looking at what the first coin is
Help them arrive at equivalent formulae, and work through some entries on the board
Instructor Notes: Help them organize it on an Excel sheet
Wow! the answers here, with up to quarters, goes to 9+ Trillion!